package link

object LinkedListDemo {
    def main(args: Array[String]): Unit = {

        val linkedList = new DoublyLinkedList[Int]
        linkedList.add(10)
        linkedList.add(20)
        linkedList.add(30)
        linkedList.add(15)

        linkedList.foreach(println)
        println("----")
        linkedList.delete(10)
        linkedList.foreach(println)
        println("----")
        linkedList.delete(22)
        linkedList.foreach(println)
        println("----")

        linkedList.add(100)
        linkedList.foreach(println)
        println("----")
    }
}
class DoublyLinkedList[T : Ordering ]{
    var head :Node =_
    var tail :Node =_

    var count:Int =0


    def add(value:T): Boolean ={
        val newNode: Node = Node(value,null,null)

        //1 先判断链表是否为空
        if(head == null){
            head = newNode
            tail = newNode
        }else{
            //2 让tail的next指向新节点
            tail.next  = newNode
            newNode.pre = tail

            //3 更新tail指向新节点
            tail = newNode

        }
        //4 count +1
        count += 1
        true
    }

    def delete(value:T):Boolean={
        find(value) match{
            case Some(node) =>
                if(node == head){
                    head = node.next  //head 指向后一个
                    head.pre = null
                }else if(node == tail){
                    tail = node.pre  //tail 指向前一个
                    tail.next = null
                }else{
                    //中间的链表去掉，在建立新的连接
                    val pre:Node = node.pre
                    val next:Node = node.next
                    pre.next =next
                    next.pre = pre
                }
                count -= 1
                true
            case None => false
        }

    }

    /**
      * 查找指定元素是否存在
      * @param value
      */
    def find(value: T): Option[Node] = {
        val ord: Ordering[T] = implicitly[Ordering[T]]
        if (head == null) return None
        else {
            var currentNode: Node = head
            while (currentNode != null) {
                if (ord.equiv(value, currentNode.value)) return Some(currentNode) //ord.equiv 是隐式召唤的内容
                currentNode = currentNode.next
            }
        }
        None
    }

    /**
      * 遍历双向链表
      * @param op
      */
    def foreach(op:T =>Unit) ={
        var currentNodeNode :Node = head

        while (currentNodeNode != null){
            op(currentNodeNode.value)
            currentNodeNode = currentNodeNode.next
        }
    }



    //表式链表中的具体节点
    case class Node(value: T, var pre: Node, var next:Node){
        override def toString: String = value.toString
    }

}